package com.algorithm.example.queue.queue.priority;

import com.algorithm.example.queue.queue.Queue;

import java.util.Iterator;

/**
 * <p>
 * 基于无序数组实现优先级队列
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/27 16:33
 */
public class PriorityQueue1<E extends Priority> implements Queue<E>, Iterable<E> {

    Priority[] array;
    int size;

    public PriorityQueue1(int capacity) {
        this.array = (E[]) new Priority[capacity + 1];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[size++] = value;
        return true;
    }

    private int selectMax() {
        int max = 0;
        for (int i = 0; i < size; i++) {
            if (array[i].Priority() < array[max].Priority()) {
                max = i;
            }
        }
        return max;
    }

    private void remove(int index) {
        if (index >= size - 1) {
            array[index] = null;
        } else {
            System.arraycopy(array, index + 1, array, index, size - index - 1);
        }
        size--;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int i = selectMax();
        E priority = (E) array[i];
        remove(i);
        return priority;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int i = selectMax();
        return (E) array[i];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = 0;

            @Override
            public boolean hasNext() {
                return p != size;
            }

            @Override
            public E next() {
                Priority priority = array[p];
                p++;
                return (E) priority;
            }
        };
    }
}
